home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1995 February: Tool Chest / Dev.CD Feb 95 / Dev.CD Feb 95.toast / New System Software Extensions / ASLM SDK v1.1.2 / ASLM Examples / TestTools / Sources / TestRandom.cp < prev    next >
Encoding:
Text File  |  1994-11-21  |  10.0 KB  |  491 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        TestRandom.cp
  3.  
  4.     Contains:    Tester for the TSimpleRandom class
  5.  
  6.     Copyright:    © 1991-1993 by Apple Computer, Inc., all rights reserved.
  7.  
  8. */
  9.  
  10. #ifndef __TESTRANDOM__
  11. #include "TestRandom.h"
  12. #endif
  13. #ifndef __STDLIB__
  14. #include <stdlib.h>
  15. #endif
  16. #ifndef __STRING__
  17. #include <String.h>
  18. #endif
  19.  
  20. #define kArraySize    513
  21. #define kIterations    100
  22.  
  23. /**********************************************************************
  24. ** PUBLIC Constructor/Destructor
  25. ***********************************************************************/
  26.  
  27. Constructor(Random)
  28. Destructor(Random)
  29.  
  30. //
  31. // Returns the square root, or the lower of the 2 numbers which straddle
  32. // the square root.
  33. //
  34. unsigned short FigSquareRoot(unsigned long num)
  35. {
  36.     unsigned short    ret = 46340;    // square root of 0x7fffffff
  37.     while (1)
  38.     {
  39.         long    func = ret*ret - num;
  40.         long    derv = ret << 1;
  41.         long    dx   = func/derv;
  42.         ret -=  (short)dx;
  43.         if (dx == 0)
  44.         {
  45.             if (func > 0)
  46.                 ret -= 1;
  47.             return ret;
  48.         }
  49.     }
  50. }
  51.  
  52. extern "C"
  53. {
  54.     #pragma parameter __D0 DoMod(__D0, __D1)
  55.     unsigned short DoMod(unsigned long, unsigned short) =
  56.     {
  57.         0x80c1, 0x4240, 0x4840
  58.         //    DIVU D1,D0; MOVE.W #0,D0; SWAP D0;
  59.     };
  60. };
  61.  
  62. //
  63. // Returns true if "num" is prime. WARNING: This routine CANNOT HANDLE EVEN NUMBERS!
  64. //
  65. Boolean IsPrime(unsigned long num)
  66. {
  67.     unsigned short    root = FigSquareRoot(num);
  68.     unsigned short    temp = (unsigned short)(num >> 16);
  69.     unsigned short    idx = temp;
  70.     ldiv_t            res;
  71.     //
  72.     // Set up idx to be the smallest odd number which will divide into "num"
  73.     // without overflowing 65535
  74.     //
  75.     if (idx < 3)
  76.         idx = 3;
  77.     else
  78.         if ((idx & 1) == 0)
  79.             idx += 1;
  80.     //
  81.     // Try and disqualify the number using the fast divide stuff first!
  82.     //
  83.     while (idx <= root)
  84.     {
  85.         if (DoMod(num, idx) == 0)            // If there is no remainder
  86.             return false;
  87.         idx += 2;
  88.     }
  89.     //
  90.     // Then do it the hard way if it passed!
  91.     //
  92.     idx =1;
  93.     if (root < temp)
  94.         temp = root;
  95.     while ((idx += 2) < temp)
  96.     {
  97.         res = ldiv(num, idx);
  98.         if (res.rem == 0)
  99.             return false;
  100.     }
  101.     return true;
  102. }
  103.  
  104. double ExpectedRuns(double total, short inParm)
  105. {
  106.     short    foo = inParm + 1;
  107.     double expect = total - total/double(foo);
  108.     while (--foo > 1)
  109.     {
  110.         expect = expect/double(foo);
  111.     }
  112.     return expect;
  113. }
  114.  
  115. /**********************************************************************
  116. ** PUBLIC InitTest
  117. ***********************************************************************/
  118.  
  119. void TTestRandom::InitTest(Boolean, Boolean, int, char**)
  120. {
  121.     TStandardPool* pool = GetPool();
  122.  
  123.     if (pool == NULL)
  124.     {
  125.         Printf("### ERROR: There is no global pool\n");
  126.         return;
  127.     }
  128.     
  129.     fTest = NULL;
  130.     
  131.     TRY
  132.         fTest = new (pool) TFastRandom;
  133.     CATCH_ALL
  134.     ENDTRY
  135.     
  136.     if (fTest == NULL)
  137.     {
  138.         Printf("### ERROR: Could not create a TSimpleRandom object\n");
  139.         return;
  140.     }
  141. }
  142.  
  143. /**********************************************************************
  144. ** PUBLIC RunTestIteration
  145. ***********************************************************************/
  146.  
  147. void TTestRandom::RunTestIteration(Boolean, Boolean)
  148. {    
  149.     unsigned long    idx;
  150.     size_t            jdx, kdx;
  151.     size_t            runs[kArraySize];
  152.     size_t            rawRuns[kArraySize];
  153.     size_t            counts[kArraySize];
  154.     size_t            rawCounts[kArraySize];
  155.     unsigned long    runPrev;
  156.     unsigned long    rawRunPrev;
  157.     unsigned long    rawPrev;
  158.     unsigned long    val;
  159.     unsigned long    rawVal;
  160.     
  161.     TStandardPool* pool = (TStandardPool*)TMemoryPool::RecoverPool(fTest);
  162.     
  163.     for (kdx = 0; kdx < 4; ++kdx)
  164.     {
  165.         char*            className;
  166.         unsigned long    small = 0x7fffffff;
  167.         unsigned long    large = 0;
  168.         unsigned long    range;
  169.         unsigned long    clos = 0x7fffffff;
  170.         size_t            count = 0;
  171.         size_t            rawCount = 0;
  172.         
  173.         memset(runs, 0, sizeof(runs));
  174.         memset(rawRuns, 0, sizeof(rawRuns));
  175.         memset(counts, 0, sizeof(counts));
  176.         memset(rawCounts, 0, sizeof(rawCounts));
  177.         
  178.         switch (kdx)
  179.         {
  180.             case 0:
  181.                 range = kMaxFastRandom;
  182.                 className = "TFastRandom";
  183.                 break;
  184.                 
  185.             case 1:
  186.                 range = kMaxSimpleRandom;
  187.                 className = "TSimpleRandom";
  188.                 delete fTest;
  189.                 fTest = new TSimpleRandom;
  190.                 break;
  191.                 
  192.             case 2:
  193.                 range = 0xffffffff;
  194.                 className = "TSimpleRandom";
  195.                 delete fTest;
  196.                 fTest = new TSimpleRandom(0, 314159261, 453448043);
  197.                 break;
  198.  
  199.             case 3:
  200.                 range = 0x7fff;
  201.                 className = "MPW Random";
  202.                 delete fTest;
  203.                 fTest = new TSimpleRandom(0x8000, 0x41c64e6d, 0x3039);
  204.                 break;
  205.         }
  206.  
  207.         size_t            divisor        = size_t(range/kArraySize) + 1;
  208.         unsigned long    each        = kIterations;
  209.         unsigned long    max            = kArraySize*each;
  210.         short            runState    = 0;
  211.         short            rawRunState    = 0;
  212.         
  213.         Printf("\nINFO: Testing class %s\n", className);
  214.             
  215.         runPrev = fTest->GetRandomNumber(1, kArraySize);
  216.         rawRunPrev = fTest->GetSeed();
  217.         rawPrev = fTest->GetSeed();
  218.         
  219.         for (idx = 0; idx < max; ++idx)
  220.         {
  221.             unsigned short    slot;
  222.             
  223.             val = fTest->GetRandomNumber(1, kArraySize);
  224.             rawVal = fTest->GetSeed();
  225.             if (val == 0 || val > kArraySize)
  226.             {
  227.                 Printf("### ERROR: Value returned was %u\n", val);
  228.                 continue;
  229.             }
  230.             counts[val - 1] += 1;
  231.             slot = (unsigned short)(rawVal/divisor);
  232.             if (slot >= kArraySize)
  233.             {
  234.                 Printf("### ERROR: Slot value was %u for %u/%u\n",
  235.                        slot, val, divisor);
  236.                 continue;
  237.             }
  238.             rawCounts[slot] += 1;
  239.  
  240.             //
  241.             // Get the largest and smallest raw values seen
  242.             //
  243.             if (rawVal > large)
  244.                 large = rawVal;
  245.             if (rawVal < small)
  246.                 small = rawVal;
  247.             //
  248.             // Get the smallest distance between 2 raw random numbers
  249.             //
  250.             unsigned long temp;
  251.             if (rawVal != rawPrev)
  252.             {
  253.                 if (rawVal > rawPrev)
  254.                     temp = rawVal - rawPrev;
  255.                 else
  256.                     temp = rawPrev - rawVal;
  257.                 if (temp < clos)
  258.                     clos = temp;
  259.             }
  260.             //
  261.             // Save the previous number
  262.             //
  263.             rawPrev = rawVal;
  264.             //
  265.             // Update Run statistics
  266.             //
  267.             switch (runState)
  268.             {
  269.                 // Just starting out, so see if we're an up or down run
  270.                 case 0:
  271.                     if (val >= runPrev)
  272.                     {
  273.                         runState = 1;
  274.                         count = 2;
  275.                     }
  276.                     else
  277.                     {
  278.                         runState = 2;
  279.                         count = 2;
  280.                     }
  281.                     break;
  282.                     
  283.                 // Handle Up Run
  284.                 case 1:
  285.                     if (val >= runPrev)
  286.                     {
  287.                         runPrev = val;
  288.                         count += 1;
  289.                     }
  290.                     else
  291.                     {
  292.                         if (count > kArraySize)
  293.                             runs[kArraySize - 1] += 1;
  294.                         else
  295.                             runs[count - 1] += 1;
  296.                         runState = 3;
  297.                     }
  298.                     break;
  299.                     
  300.                 // Handle Down Run
  301.                 case 2:
  302.                     if (val <= runPrev)
  303.                     {
  304.                         runPrev = val;
  305.                         count += 1;
  306.                     }
  307.                     else
  308.                     {
  309.                         if (count > kArraySize)
  310.                             runs[kArraySize - 1] += 1;
  311.                         else
  312.                             runs[count - 1] += 1;
  313.                         runState = 4;
  314.                     }
  315.                     break;
  316.                     
  317.                 // After Up Run
  318.                 case 3:
  319.                     runPrev = val;
  320.                     count = 1;
  321.                     runState = 2;
  322.                     break;
  323.                     
  324.                 // After Down Run
  325.                 case 4:
  326.                     runPrev = val;
  327.                     count = 1;
  328.                     runState = 1;
  329.                     break;
  330.                     
  331.             }
  332.             //
  333.             // Update Run statistics
  334.             //
  335.             switch (rawRunState)
  336.             {
  337.                 // Just starting out, so see if we're an up or down run
  338.                 case 0:
  339.                     if (rawVal >= rawRunPrev)
  340.                     {
  341.                         rawRunState = 1;
  342.                         rawCount = 2;
  343.                     }
  344.                     else
  345.                     {
  346.                         rawRunState = 2;
  347.                         rawCount = 2;
  348.                     }
  349.                     break;
  350.                     
  351.                 // Handle Up Run
  352.                 case 1:
  353.                     if (rawVal >= rawRunPrev)
  354.                     {
  355.                         rawRunPrev = rawVal;
  356.                         rawCount += 1;
  357.                     }
  358.                     else
  359.                     {
  360.                         if (rawCount > kArraySize)
  361.                             rawRuns[kArraySize - 1] += 1;
  362.                         else
  363.                             rawRuns[rawCount - 1] += 1;
  364.                         rawRunState = 3;
  365.                     }
  366.                     break;
  367.                     
  368.                 // Handle Down Run
  369.                 case 2:
  370.                     if (rawVal <= rawRunPrev)
  371.                     {
  372.                         rawRunPrev = rawVal;
  373.                         rawCount += 1;
  374.                     }
  375.                     else
  376.                     {
  377.                         if (rawCount > kArraySize)
  378.                             rawRuns[kArraySize - 1] += 1;
  379.                         else
  380.                             rawRuns[rawCount - 1] += 1;
  381.                         rawRunState = 4;
  382.                     }
  383.                     break;
  384.                     
  385.                 // After Up Run
  386.                 case 3:
  387.                     rawRunPrev = rawVal;
  388.                     rawCount = 1;
  389.                     rawRunState = 2;
  390.                     break;
  391.                     
  392.                 // After Down Run
  393.                 case 4:
  394.                     rawRunPrev = rawVal;
  395.                     rawCount = 1;
  396.                     rawRunState = 1;
  397.                     break;
  398.                     
  399.             }
  400.         }
  401.         if (count > kArraySize)
  402.             runs[kArraySize - 1] += 1;
  403.         else
  404.             runs[count - 1] += 1;
  405.         if (rawCount > kArraySize)
  406.             rawRuns[kArraySize - 1] += 1;
  407.         else
  408.             rawRuns[rawCount - 1] += 1;
  409.         //
  410.         // Output Chi-Squared statistic
  411.         //
  412.         {
  413.             double    a = 0.0;
  414.             double    b = double(each);
  415.             for (jdx = 0; jdx < kArraySize; ++jdx)
  416.             {
  417.                 double    y = double(counts[jdx]) - b;
  418.                 a = a + (y*y);
  419.             }
  420.             a = a/b;
  421.             unsigned long val = (unsigned long)(a*100);
  422.             Printf("INFO: Chi-Squared value for Process Data was %u.%02u\n",
  423.                    val/100, val % 100);
  424.             
  425.             a = 0.0;
  426.             for (jdx = 0; jdx < kArraySize; ++jdx)
  427.             {
  428.                 double    y = double(rawCounts[jdx]) - b;
  429.                 a = a + (y*y);
  430.             }
  431.             a = a/b;
  432.             val = (unsigned long)(a*100);
  433.             Printf("INFO: Chi-Squared value for Raw Data was %u.%02u\n",
  434.                    val/100, val % 100);
  435.         }
  436.         //
  437.         // Output Run statistic statistic
  438.         //
  439.         {
  440.             size_t    total = 0;
  441.             for (jdx = 0; jdx < kArraySize; ++jdx)
  442.                 total += runs[jdx];
  443.             double y = 0.0;
  444.             double b = double(total);
  445.             for (jdx = 0; jdx < 9; ++jdx)
  446.             {
  447.                 double c = ExpectedRuns(b, (short)jdx + 1);
  448.                 double d = double(runs[jdx]) - c;
  449.                 y = y + (d*d)/c;
  450.             }
  451.             unsigned long val = (unsigned long)(y*100);
  452.             Printf("INFO: Chi-Squared value for Processed Data Runs was %u.%02u\n",
  453.                   val/100, val % 100);
  454.             for (jdx = 9; jdx < kArraySize; ++jdx)
  455.                 if (runs[jdx] > 1)
  456.                     Printf("WARNING: Runs for #%u was %u\n", jdx + 1, runs[jdx]);
  457.             total = 0;
  458.             for (jdx = 0; jdx < kArraySize; ++jdx)
  459.                 total += rawRuns[jdx];
  460.             y = 0.0;
  461.             b = double(total);
  462.             for (jdx = 0; jdx < 9; ++jdx)
  463.             {
  464.                 double c = ExpectedRuns(b, (short)jdx + 1);
  465.                 double d = double(rawRuns[jdx]) - c;
  466.                 y = y + (d*d)/c;
  467.             }
  468.             val = (unsigned long)(y*100);
  469.             Printf("INFO: Chi-Squared value for Raw Data Runs was %u.%02u\n",
  470.                   val/100, val % 100);
  471.             for (jdx = 9; jdx < kArraySize; ++jdx)
  472.                 if (rawRuns[jdx] > 1)
  473.                     Printf("WARNING: Runs for #%u was %u\n", jdx + 1, rawRuns[jdx]);
  474.         }
  475.         Printf("INFO: smallest was %lu, largest was %lu, out of %lu\n",
  476.                small, large, range);
  477.         Printf("INFO: Closest numbers were separated by %lu\n",
  478.                clos);
  479.     }
  480. }
  481.  
  482. /**********************************************************************
  483. ** PUBLIC EndTest
  484. ***********************************************************************/
  485.  
  486. void TTestRandom::EndTest(Boolean verbose, Boolean)
  487. {
  488.     if (verbose)
  489.         Printf("INFO: End of Random test\n");
  490. }
  491.